//
//  HeaderFile.swift
//  SFQuestion
//
//  Created by sr liu on 2021/7/18.
//

import Foundation

/*
 树的性质
 
 
 
 
 
 */





//MARK:-链表
public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

public class RandomListNode {
    public var label: Int
    public var next: RandomListNode?
    public var random: RandomListNode?
    public init(_ label: Int = 0, _ next: RandomListNode? = nil, _ random: RandomListNode? = nil) {
        self.label = label
        self.next = next
        self.random = random
    }
}

extension RandomListNode: Hashable, Equatable {
  public func hash(into hasher: inout Hasher) {
    // 用于唯一标识
    hasher.combine(label)
    hasher.combine(ObjectIdentifier(self))
  }
  public static func ==(lhs: RandomListNode, rhs: RandomListNode) -> Bool {
    return lhs === rhs
  }
}

//MARK:-二叉树
public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}
//包含指向父节点的next指针
public class TreeLinkNode {
  public var val: Int
  public var left: TreeLinkNode?
  public var right: TreeLinkNode?
  public var next: TreeLinkNode?
  public init(_ val: Int=0, _ left: TreeLinkNode?=nil, _ right: TreeLinkNode?=nil, _ next: TreeLinkNode?=nil) {
    self.val = val
    self.left = left
    self.right = right
    self.next = next
  }
}

//MARK:-递归遍历二叉树
func preOrderRecursion(_ root: TreeNode?) {
    if let tree = root {
        print(tree.val)
        preOrderRecursion(tree.left)
        preOrderRecursion(tree.right)
    }
}

//MARK:-非递归遍历二叉树
func preOrderNoRecursion(_ root: TreeNode?) {
    guard let tree = root else {
        print("nil tree")
        return
    }
    //创建栈容器和游标
    var stack: [TreeNode] = [TreeNode]()
    var node:TreeNode? = tree
    while node != nil || stack.count > 0 {
        while node != nil {//每一课子树往左走到头
            print(node!.val)
            stack.append(node!)
            node = node?.left
        }
        if stack.count > 0 {//回头拿右子树
            node = stack.removeLast()
            node = node?.right
        }
    }
    
}


//MARK:-创建二叉树
/// 使用数组创建二叉树
/// - Parameter nodes: 前序遍历的整数数组-1代表无此节点 应该是层序
/// - Returns: 二叉树
func createBiTree(_ nums:[Int]) -> TreeNode? {
    var root: TreeNode? = nil
    if nums.count > 0 {
        root = createBiTreeCoreBFS(nums, 0)
    }
    return root
}


func createBiTreeCoreBFS(_ nums:[Int], _ index:Int) -> TreeNode? {
    let len = nums.count
    if len == 0 || index >= len || nums[index] == -1 {
        return nil
    }
    let tree = TreeNode.init(nums[index])
    tree.left = createBiTreeCoreBFS(nums, 2 * index + 1)
    tree.right = createBiTreeCoreBFS(nums, 2 * index + 2)
    return tree
}


/// 替换某个位置字符串
/// - Parameters:
///   - a: 原字符串
///   - i: 要替换的字符下标位置，0开始
///   - sub: 替换成的字符串
/// - Returns: 新字符串
func replaceStr(_ a: String, _ i: Int, _ sub: String) -> String {
    let a = a
    if i >= a.count {
        return a
    }
    let startIndex = a.index(a.startIndex, offsetBy: i)
    let endIndex = a.index(after: startIndex)
    return a.replacingCharacters(in: startIndex..<endIndex, with: sub)
}

/*
 NSRange的方法替换字符串
 let levels = "ABCDE"
 let nsRange = NSMakeRange(1, 4)
 let tepLevel = (levels as NSString).replacingCharacters(in: nsRange, with: "AAAA")
 print("tepLevel:\(tepLevel)")
 
 String.Index.init(encodedOffset: 1)
 
 var s = "Swift"
 let range = s.range(of: "w")
 
 if (range != nil) {
     print(s.replacingCharacters(in: range!, with: "A"))
 }
 */

//一些类型的转换,常用的方法名字要记住,便于做题
func convertTools() {
    //字符串转数组,取字符,字符字母转换
    var string: String = "abcde"
    var strArray = Array(string)
    var character = (string as NSString).character(at: 1)
    var character2 = strArray[1]
    var num = Int(character)
    var character3 = Character(UnicodeScalar(num)!)
    
    //数组
    var nums = [Int]()
    nums.append(1)
    nums.append(2)
    nums.contains(2)
    nums.isEmpty
    nums.count
    nums.swapAt(0, nums.count - 1)
    nums.reverse()
    (1...5).reversed()//遍历时用
    //注意这时候不要nums[i]会越界
    var nums2 = Array.init(repeating: 0, count: 5)
    //子串操作
    //常用方法总结
    
    var a = 1
    var b = 2
    max(a, b)
    min(a, b)
    
    var ch = "a"
    switch ch {
    case "a":
        print("a")
    default:
        print("de")
    }
    
    var dic = [0:1]
    //字典还可以先写default 不用判断可选了。。
    let v = dic[1, default: 1]
    print(dic)
    print(v)
}
